package leetcode.day;

public class MaximumDifference {

    public static void main(String[] args) {
        System.out.println(maximumDifference(new int[]{1, 5, 2, 10}));
    }

    // 暴力
    public static int maximumDifference(int[] nums) {
        int max = Integer.MIN_VALUE;
        for (int i = nums.length - 1; i >= 0; i--) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    max = Math.max(nums[i] - nums[j], max);
                }
            }

        }
        return max == Integer.MIN_VALUE ? -1 : max;
    }

    // 贪心
    public int maximumDifference2(int[] nums) {
        int n = nums.length, ans = -1;
        int min = nums[0];
        for (int i = 0; i < n; i++) {
            if (nums[i] > min) {
                ans = Math.max(ans, nums[i] - min);
            }
            min = Math.min(min, nums[i]);
        }
        return ans;
    }


}
